﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace MathService.Graphs
{
    public static class GraphEx
    {
        //public static void Test()
        //{
        //    //        var M = new[,]
        //    //        { /* 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14*/
        //    // /*  0 */   {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /*  1 */   {1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /*  2 */   {1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /*  3 */   {0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
        //    // /*  4 */   {0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
        //    // /*  5 */   {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
        //    // /*  6 */   {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
        //    // /*  7 */   {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /*  8 */   {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /*  9 */   {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /* 10 */   {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /* 11 */   {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /* 12 */   {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /* 13 */   {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        //    // /* 14 */   {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        //    //        };

        //    // var P = new[,]
        //    // {
        //    //    {false, true, true, true, true, true, false, false},
        //    //    {false, false, true, false, true, false, false, false},
        //    //    {false, false, false, true, false, false, false, false},
        //    //    {false, false, false, false, true, false, false, false},
        //    //    {false, false, false, false, false, true, false, false},
        //    //    {false, false, true, false, false, false, true, true},
        //    //    {false, false, false, false, false, true, false, true},
        //    //    {false, false, false, false, false, true, true, false}
        //    // };

        //    // var dir = new DirectoryInfo("c:\\");
        //    // var root = dir.AsGraphNode(d => d.GetDirectories(), (from, to) => dir.GetFilesCount());

        //    // var root1 = new { M, i = 0 }
        //    //    .AsGraphNode(r => Enumerable.Range(0, r.M.GetLength(1)).Select(i => new { M, i }),
        //    //        (from, to) => from.M[to.i, from.i]);


        //    //var root2 = root1.AsGraphNode(node => node.Links.Where(link => link.Weight == 1)
        //    //    .Select(link => link.Node),
        //    //    (from, to) => to.Value.i - from.Value.i);
        //    //var R = root2.GetWaveRouth();

        //    //typeof (List<int>).AsGraphNode
        //    //    (
        //    //        type => type.GetProperties(BindingFlags.Public|BindingFlags.Instance)
        //    //            .Select(p => p.PropertyType),
        //    //        (From, to) => From.Name
        //    //    );
        //}

        /// <summary>Преобразование к типу вершины графа</summary>
        /// <typeparam name="V">Тап значения вершины</typeparam>
        /// <typeparam name="W">Тип веса связи</typeparam>
        /// <param name="value">Значение вершины</param>
        /// <param name="GetChields">Метод выделения дочерних узлов</param>
        /// <param name="GetWeight">Метод определения веса связи между узлами</param>
        /// <param name="Buffered">Буферизация узлов и связей</param>
        /// <returns>Узел графа</returns>
        /// <example>
        /// <code>
        /// var M = new[,]
        ///        { /* 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14*/
        /// /*  0 */   {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /*  1 */   {1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /*  2 */   {1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /*  3 */   {0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},
        /// /*  4 */   {0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
        /// /*  5 */   {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0},
        /// /*  6 */   {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1},
        /// /*  7 */   {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /*  8 */   {0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /*  9 */   {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /* 10 */   {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /* 11 */   {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /* 12 */   {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /* 13 */   {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        /// /* 14 */   {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        ///        };
        /// var node = new { M, i = 0 };
        /// var root = node.AsGraphNode(r => Enumerable.Range(0, r.M.GetLength(1)).Select(i => new { M, i }),
        ///              (from, to) => from.M[to.i, from.i]);
        /// var tree = root.AsGraphNode(root => root.Links.Where(link => link.Weight == 1)
        ///                                               .Select(link => link.Node),
        ///                             (from, to) => to.Value.i - from.Value.i);
        /// var rouht = tree.GetWaveRouth();
        /// 
        /// </code>
        /// </example>
        public static IGraphNode<V, W> AsGraphNode<V, W>
            (
                this V value,
                Func<V, IEnumerable<V>> GetChields,
                Func<V, V, W> GetWeight,
                bool Buffered = false
            )
        {
            return new LambdaGraphNode<V, W>(value, GetChields, GetWeight, Buffered);
        }

        /// <summary>Преобразование к виду графа</summary>
        /// <typeparam name="V">Тип преобразуемого объекта</typeparam>
        /// <param name="value">Преобразуемый объект</param>
        /// <param name="GetChields">Метод извлечения дочерних узлов из каждого узла графа</param>
        /// <param name="Buffered">Флаг необходимости проведения буфферизации</param>
        /// <returns></returns>
        public static IGraphNode<V> AsGraphNode<V>(this V value, Func<V, IEnumerable<V>> GetChields, bool Buffered = false)
        {
            return new LambdaGraphNode<V>(value, GetChields, Buffered);
        }

        /// <summary>Метод перебора вершин графа путём обхода "в глубину". Обход на основе стека дочерних узлов.</summary>
        /// <typeparam name="V">Тип узлов графа</typeparam>
        /// <typeparam name="W">Тип связи узлов графа</typeparam>
        /// <param name="Node">Начальный узел графа</param>
        /// <returns>Последовательность узлов графа</returns>
        public static IEnumerable<IGraphNode<V, W>> BypassInDepth<V, W>(this IGraphNode<V, W> Node)
        {
            var stack = new Stack<IGraphNode<V, W>>();
            stack.Push(Node);
            var visited = new List<IGraphNode<V, W>>();
            do
            {
                do { Node = stack.Pop(); } while(visited.Contains(Node));
                yield return Node;
                visited.Add(Node);
                Node.Links.Select(l => l.Node)
                            .Where(node => !stack.Contains(node) && !visited.Contains(node))
                            .ToArray()
                            .GetReversed()
                            .Foreach(stack.Push);
            } while(stack.Count != 0);
        }

        /// <summary>Метод перебора вершин графа путём обхода "в глубину". Обход на основе стека дочерних узлов.</summary>
        /// <typeparam name="V">Тип узлов графа</typeparam>
        /// <param name="Node">Начальный узел графа</param>
        /// <returns>Последовательность узлов графа</returns>
        public static IEnumerable<IGraphNode<V>> BypassInDepth<V>(this IGraphNode<V> Node)
        {
            var stack = new Stack<IGraphNode<V>>();
            stack.Push(Node);
            var visited = new List<IGraphNode<V>>();
            do
            {
                do { Node = stack.Pop(); } while(visited.Contains(Node));
                yield return Node;
                visited.Add(Node);
                Node.Where(node => !stack.Contains(node) && !visited.Contains(node))
                    .ToArray()
                    .GetReversed()
                    .Foreach(stack.Push);
            } while(stack.Count != 0);
        }

        /// <summary>Метод перебора вершин графа путём обхода "в ширину". Обход на основе очереди дочерних узлов.</summary>
        /// <typeparam name="V">Тип узлов графа</typeparam>
        /// <typeparam name="W">Тип связи узлов графа</typeparam>
        /// <param name="Node">Начальный узел графа</param>
        /// <returns>Последовательность узлов графа</returns>
        public static IEnumerable<IGraphNode<V, W>> BaypassInWidth<V, W>(this IGraphNode<V, W> Node)
        {
            var queue = new Queue<IGraphNode<V, W>>();
            queue.Enqueue(Node);
            var visited = new List<IGraphNode<V, W>>();
            do
            {
                Node = queue.Dequeue();
                yield return Node;
                visited.Add(Node);
                Node.Links.Select(l => l.Node)
                            .Where(node => !queue.Contains(node) && !visited.Contains(node))
                            .Foreach(queue.Enqueue);
            } while(queue.Count != 0);
        }

        /// <summary>Метод перебора вершин графа путём обхода "в ширину". Обход на основе очереди дочерних узлов.</summary>
        /// <typeparam name="V">Тип узлов графа</typeparam>
        /// <param name="Node">Начальный узел графа</param>
        /// <returns>Последовательность узлов графа</returns>
        public static IEnumerable<IGraphNode<V>> BaypassInWidth<V>(this IGraphNode<V> Node)
        {
            var queue = new Queue<IGraphNode<V>>();
            queue.Enqueue(Node);
            var visited = new List<IGraphNode<V>>();
            do
            {
                Node = queue.Dequeue();
                yield return Node;
                visited.Add(Node);
                Node.Where(node => !queue.Contains(node) && !visited.Contains(node))
                    .Foreach(queue.Enqueue);
            } while(queue.Count != 0);
        }

        /// <summary>МЕтод поиска пути в графе путём обхода вершин "в глубину"</summary>
        /// <typeparam name="V">Тип вершины графа</typeparam>
        /// <typeparam name="W">Тип связи вершин графа</typeparam>
        /// <param name="RootNode">Начальный элемент поиска пути</param>
        /// <param name="FindPredicate">Метод определения окончания поиска, как успешного</param>
        /// <returns>Маршрут в графе</returns>
        public static GraphRouth<V, W> FindRouthInDepth<V, W>(this IGraphNode<V, W> RootNode, Predicate<V> FindPredicate)
        {
            var stack = new Stack<IGraphNode<V, W>>();
            var Node = RootNode;
            stack.Push(Node);
            var visited = new List<IGraphNode<V, W>>();
            var RouthStack = new Stack<IGraphNode<V, W>>();
            do
            {
                do { Node = stack.Pop(); } while(visited.Contains(Node));
                RouthStack.Push(Node);

                if(FindPredicate(Node.Value))
                    return new GraphRouth<V, W>(RouthStack.Reverse());

                visited.Add(Node);
                var next = Node.Links.Select(l => l.Node)
                           .Where(node => !stack.Contains(node) && !visited.Contains(node))
                           .ToArray()
                           .GetReversed();

                if(next.Length == 0)
                {
                    while(RouthStack.Count > 0
                        && RouthStack.Peek().Links.All(l => visited.Contains(l.Node)))
                        RouthStack.Pop();
                }
                next.Foreach(stack.Push);
            } while(stack.Count != 0);

            return new GraphRouth<V, W>(new IGraphNode<V, W>[0]);
        }

        /// <summary>Метод поиска всех путей из указанной вершины до всех доступных вершин графа методом фронта волны</summary>
        /// <typeparam name="V">Тип вершины графа</typeparam>
        /// <typeparam name="W">Тип связи вершин графа</typeparam>
        /// <param name="Root">Начальный элемент поиска пути</param>
        /// <returns>Массив найденных путей</returns>
        public static GraphRouth<V, W>[] GetWaveRouth<V, W>(this IGraphNode<V, W> Root)
        {
            var visited = new List<IGraphNode<V, W>>();
            var queue = new Queue<Stack<IGraphNode<V, W>>>();
            var stack = new Stack<IGraphNode<V, W>>();
            stack.Push(Root);
            visited.Add(Root);
            queue.Enqueue(stack);
            var result = new List<GraphRouth<V, W>>();
            do
            {
                var R = queue.Dequeue();
                var wave = R.Peek().Links.Select(l => l.Node).Where(n => !visited.Contains(n)).ToArray();
                if(wave.Length == 0)
                {
                    result.Add(new GraphRouth<V, W>(R.ToArray().GetReversed()));
                    continue;
                }
                foreach(var node in wave)
                {
                    visited.Add(node);
                    var r = new Stack<IGraphNode<V, W>>(R.Reverse());
                    r.Push(node);
                    queue.Enqueue(r);
                }
            } while(queue.Count > 0);
            return result.ToArray();
        }
    }
}